\documentclass[DaoFP]{subfiles}
\begin{document}
\setcounter{chapter}{14}

\chapter{Monads}

When monads are explained in the context of programming, it's hard to see the common pattern while focusing on the functors. To understand monads you have to look inside functors and read between the lines of code. It is sometimes said that monads let us overload the semicolons. That's because in many imperative languages semicolons are used for sequencing operations. In functional languages, monads play the role of sequencing effectful computations.

\section{Sequential Composition of Effects}

Parallel composition as special case of sequential composition.

---

The way effectful computations are composed in imperative languages is to use regular function composition for the values and let the side effects combine themselves willy-nilly. 

When we represent effectful computations as pure functions, we are faced with the problem of composing two functions of the form
\begin{haskell}
g :: a -> f b
h :: b -> f c
\end{haskell}
In all cases of interest the type constructor \hask{f} happens to be a \hask{Functor}, so we'll assume that in what follows.

The naive approach would be to unpack the result of the first function, pass the value to the next function, then compose the effects of both functions on the side, and combine them with the result of the second function. This is not always possible, even for cases that we have studied so far, much less for an arbitrary type constructor.

For the sake of the argument, it's instructive to see how we could do it for the \hask{Maybe} functor. If the first function returns \hask{Just}, we pattern match it to extract the contents and call the next function with it.

But if the first function returns \hask{Nothing}, we have no value with which to call the second function. We have to short-circuit it, and return \hask{Nothing} directly. So composition is possible, but it means modifying flow of control by skipping the second call based on the side effect of the first call. 

For some functors the composition of side effects is possible, for others it's not. How can we characterize those ``good'' functors?

For a functor to encode composable side effects we must at least be able to implement the following polymorphic higher-order function: 
\begin{haskell}
composeWithEffects :: Functor f => 
       (b -> f c) -> (a -> f b) -> (a -> f c)
\end{haskell}
This is very similar to regular function composition:
\begin{haskell}
(.) :: (b -> c) -> (a -> b) -> (a -> c)
\end{haskell}
so it's natural to ask if there is a category in which the former defines a composition of arrows. Let's see what more is needed to construct such a category.

Objects in this new category are the same Haskell types as before. But an arrow, which we'll write as $a \twoheadrightarrow b$, is implemented as a Haskell function:
\begin{haskell}
g :: a -> f b
\end{haskell}
Our \hask{composeWithEffects} can then be used to implement the composition of such arrows. 

To have a category, we require that this composition be associative. We also need an identity arrow for every object \hask{a}. This is an arrow $a \twoheadrightarrow a$, so it corresponds to a Haskell function:
\begin{haskell}
idWithEffects :: a -> f a
\end{haskell}
It must behave like identity with respect to \hask{composeWithEffects}.

Another way of looking at this arrow is that it lets you add a trivial effect to any value of type \hask{a}. It's the effect that combined with any other effect does nothing to it. We've seen this before in the definition of \hask{pure} for \hask{Applicative} functors. 

We have just defined a monad! After some renaming and rearranging, we can write it as a typeclass:
\begin{haskell}
class Functor m => Monad m where
  (<=<) :: (b -> m c) -> (a -> m b) -> (a -> m c)
  return :: a -> m a
\end{haskell}
The infix operator \hask{<=<} replaces the function \hask{composeWithEffects}. The \hask{return} function is the identity arrow in our new category. (This is not the definition of the monad you'll find in the Haskell's \hask{Prelude} but, as we'll see soon, it's equivalent to it.)

As an exercise, let's define the \hask{Monad} instance for \hask{Maybe}. The ``fish'' operator \hask{<=<} composes two functions:
\begin{haskell}
f :: a -> Maybe b
g :: b -> Maybe c
\end{haskell}
into one function of the type \hask{a -> Maybe c}. The unit of this composition, \hask{return}, encloses a value in the \hask{Just} constructor.
\begin{haskell}
instance Monad Maybe where
  g <=< f = \a -> case f a of
                    Nothing -> Nothing
                    Just b -> g b
  return = Just  
\end{haskell}

You can easily convince yourself that category laws are satisfied. In particular the composition \hask{ return <=< g } is the same as \hask{g} and \hask{ f <=< return } is the same as \hask{f}. The proof of associativity is also pretty straightforward: If any of the functions returns \hask{Nothing}, the result is \hask{Nothing}; otherwise it's just a straightforward function composition, which is associative.

The category that we have just defined is called the \index{Kleisli category}\emph{Kleisli category} for the monad \hask{m}. The functions \hask{a -> m b} are called the \index{Kleisli arrow}\emph{Kleisli arrows}. They compose using \hask{<=<} and the identity arrow is called \hask{return}.

All effects listed in the section on effects are \hask{Monad} instances. If you look at them as type constructors, it's hard to see any similarities between them. Each effect is different. The thing they have in common is that they can be used to implement \emph{composable} Kleisli arrows. 

As Lao Tzu would say: Composition is something that happens \emph{between} things. While focusing our attention on things, we often lose sight of what's in the gaps. 

\section{Alternative Definitions}

The definition of a monad using Kleisli arrows has the advantage that the monad laws are simply the associativity and the unit laws of a Kleisli category. There are two other equivalent definitions of a monad, one preferred by mathematicians, and one by programmers. 

First, let's notice that the fish operator takes two functions as arguments. The only thing that a function is useful for is to be applied to an argument. When we apply the first function \hask{ f :: a -> m b } we get a value of the type \hask{ m b}. At this point we would be stuck, if it weren't for the fact that \hask{m} is a functor. Functoriality lets us apply the second function \hask{ g :: b -> m c } to \hask{ m b}. Indeed the lifting of \hask{g} by \hask{m} is of the type:
\begin{haskell}
m b -> m (m c)
\end{haskell}
This is almost the result we are looking for. If we could only flatten \hask{m(m c)} to \hask{m c}. This flattening, id it's possible, is called \hask{join}. In other words, if we were given:
\begin{haskell}
join ::  m (m a) -> m a
\end{haskell}
we could implement \hask{<=<}:
\begin{haskell}
g <=< f = \a -> join (fmap g (f a))
\end{haskell}
or, using point free notation:
\begin{haskell}
g <=< f = join . fmap g . f
\end{haskell}

Conversely, we could implement \hask{join} in terms of \hask{<=<}:
\begin{haskell}
join = id <=< id
\end{haskell}
The latter definition may not be immediately obvious, until you realize that the rightmost \hask{id} is applided to \hask{m (m a)}, and the leftmost one is applied to \hask{m a}. We re-interpret a Haskell function:
\begin{haskell}
m (m a) -> m (m a)
\end{haskell}
as an arrow in the Kleisli category $ m (m a) \twoheadrightarrow m a$. Similarly, the function:
\begin{haskell}
m a -> m a
\end{haskell}
implements a Kleisli arrow $m a \twoheadrightarrow a$. Their Kleisli composition produces a Kleisli arrow $m (m a) \twoheadrightarrow a$ or a Haskell function:
\begin{haskell}
m (m a) -> m a
\end{haskell}

This leads us to the equivalent definition of a monad in terms of \hask{join} and \hask{return}:
\begin{haskell}
class Functor m => Monad m where
  join :: m (m a) -> m a
  return :: a -> m a
\end{haskell}

This is still not the definition you will find in the standard Haskell \hask{Prelude}. Since the fish operator is a generalization of the dot operator, using it is equivalent to point-free programming. It lets us compose arrows without naming intermediate values. Although some consider point-free programs more elegant, most programmers find them difficult to follow. 

Programmatically, sequential function composition is really done in two steps: We apply the first function, then apply the second function to the result. Explicitly naming the intermediate result is often helpful in understanding what's going on.

To do the same with Kleisli arrows, we have to know how to apply the second Kleisli arrow to a named monadic value---the result of the first Kleisli arrow. The function that does that is called \emph{bind} and is written as an infix operator:
\begin{haskell}
(>>=) :: m a -> (a -> m b) -> m b
\end{haskell}
Obviously, we can implement Kleisli composition in terms of bind:

\begin{haskell}
g <=< f = \a -> (f a) >>= g
\end{haskell}

Conversely, bind can be implemented in terms of the Kleisli arrow:
\begin{haskell}
ma >>= k = (k <=< id) ma
\end{haskell}

This leads us to the following definition:
\begin{haskell}
class Monad m where
  (>>=) :: m a -> (a -> m b) -> m b
  return :: a -> m a 
\end{haskell}
This is almost the definition you'll find in the \hask{Prelude}, except for the additional \hask{Applicative} constraint. We'll talk about it next.

We can also implement \hask{join} using bind:
\begin{haskell}
join  :: (Monad m) => m (m a) -> m a
join mma =  mma >>= id
\end{haskell}
The Haskell function \hask{id} goes from \hask{m a} to \hask{m a} or, as a Kleisli arrow, $m a \twoheadrightarrow a$.

Interestingly, a \hask{Monad} defined using bind is automatically a functor. The lifting function for it is called \hask{liftM}
\begin{haskell}
liftM :: Monad m => (a -> b) -> (m a -> m b)
liftM f ma = ma >>= (return . f)
\end{haskell}

\subsection{Monad as Applicative}

In a cartesian category every monad is lax monoidal. Indeed, if you know how to compose effectful computations sequentially, you know how to compose them in parallel. If the result of the first computation is not used as the input to the second computation, they can be done in parallel. The effects, on the other hand, are always composed sequentially. 

In Haskell, we can define the \hask{Monoidal} instance for any \hask{Monad}:
\begin{haskell}
instance Monad m => Monoidal m where
    unit = return ()
    ma >*< mb = ma >>= 
         (\a -> mb >>= 
             \b -> return (a, b))
\end{haskell}
You'll notice that the final \hask{return} needs access to both \hask{a} and \hask{b}, which are defined in outer environments. This would be impossible without the monad being strong.

As we discussed earlier, every Haskell functor is strong, so every monad in Haskell is strong by virtue of being a functor. This is important, because we want monadic code to have access to the environment. 


Iin a cartesian \emph{closed} category, every monad\footnote{Again, the correct incantation is ``every enriched monad''}, being \hask{Monoidal}, is automatically \hask{Applicative}. We can show it directly by implementing \hask{ap}, which has the same type signature as the splat operator:
\begin{haskell}
ap :: (Monad m) => m (a -> b) -> m a -> m b
ap fs as = fs >>= 
    (\f -> as >>= 
        \a -> return (f a))
\end{haskell}
We can also use monadic \hask{return} as applicative \hask{pure}.

This relationship between monads and applicatives is expressed in Haskell by making \hask{Applicative} a superclass of \hask{Monad}:
\begin{haskell}
class Applicative m => Monad m where
    (>>=)       :: forall a b. m a -> (a -> m b) -> m b
    return      :: a -> m a
    return      = pure
\end{haskell}

The converse is not true: not every \hask{Applicative} is a \hask{Monad}. The standard counterexample is the \hask{Applicative} instance for the list functor encapsulated in \hask{ZipList}.

When instantiating a monad for a Haskell type constructor, we split the definition between three type classes: \hask{Functor}, \hask{Applicative}, and \hask{Monad}. In most cases the \hask{Functor} instance can be automatically derived. If we don't already have the complete \hask{Applicative} instance handy, we use \hask{ap} to define the splat operator. The order in which the \hask{Applicative} and the \hask{Monad} instances are defined is irrelevant.


Let's illustrate this in a toy example:
\begin{haskell}
data Id a = MakeId { getId :: a }
    deriving Functor
\end{haskell}
The \hask{Applicative} instance defines \hask{pure} and \hask{<*>}:
\begin{haskell}
instance Applicative Id where
    pure = MakeId 
    (<*>) = ap
\end{haskell}
The latter uses the \hask{ap} function that is defined in \hask{Control.Monad}:
\begin{haskell}
import Control.Monad (ap)
\end{haskell}
Finally, bind is defined in the \hask{Monad} instance:
\begin{haskell}
instance Monad Id where
    ma >>= k = k (getId ma)
\end{haskell}
In modern Haskell applicative \hask{pure} replaces the monadic \hask{return}.

In programming, monad is more powerful than applicative. That's because monadic code lets you examine the contents of a monadic value and branch depending on it. 

Applicative composition using the splat operator doesn't allow for one part of the computation to inspect the result of the other. This limitation is turned into an advantage when performing parallel computations.

\section{Monad Instances}

We are now ready to define monad instances for the functors we used for side effects. This will allow us to compose side effects.

\subsection{Partiality}
We've already seen the version of the \hask{Maybe} monad implemented using Kleisli composition. Here's the more familiar implementation using bind:
\begin{haskell}
instance Monad Maybe where
  Nothing  >>= k = Nothing
  (Just a) >>= k = k a
\end{haskell}
As usual, \hask{pure} or \hask{return} is implemented in the \hask{Applicative} instance:
\begin{haskell}
  pure = Just
\end{haskell}

\subsection{Logging}
\hask{Writer} is a thin encapsulation of a pair:
\begin{haskell}
newtype Writer w a = Writer { runWriter :: (a, w) }
\end{haskell}

In order to compose functions that produce logs, we need a way to combine individual log entries using a \hask{Monoid}:
\begin{haskell}
instance Monoid w => Monad (Writer w) where
  (Writer (a, w)) >>= k = let (Writer (b, w')) = k a
                          in Writer (b, mappend w w')
\end{haskell}
The \index{\hask{let}}\hask{let} clause can not only introduce local bindings, but can also do pattern matching.

With \hask{pure} implemented in the \hask{Applicative} instance:
\begin{haskell}
  pure a = Writer (a, mempty)
\end{haskell}

\subsection{Environment}

The reader monad is a thin encapsulation of a function from the environment to the return type:
\begin{haskell}
newtype Reader e a = Reader { runReader :: e -> a }
\end{haskell}
Here's the \hask{Monad} instance:
\begin{haskell}
instance Monad (Reader e) where
  ma >>= k = Reader (\e -> let a = runReader ma e
                           in runReader (k a) e)
\end{haskell}

With \hask{pure} implemented in the \hask{Applicative} instance:
\begin{haskell}
  pure a = Reader (\e -> a)
\end{haskell}
The implementation of bind for the reader monad creates a function that takes the environment as its argument. This environment is used twice, first to run \hask{ma} to get the value of \hask{a}, and then to evaluate the value produced by \hask{k a}.

The implementation of \hask{pure} ignores the environment.

\begin{exercise}
Define the \hask{Functor} and the \hask{Monad} instance for the following data type:
\begin{haskell}
newtype E e a = E { runE :: e -> Maybe a }
\end{haskell}
\end{exercise}


\subsection{State}
Like reader, the state monad is a function type:
\begin{haskell}
newtype State s a = State { runState :: s -> (a, s) }
\end{haskell}
Its bind is similar, except that the result of \hask{k} acting on  \hask{a} has to be run with the modified state \hask{s'}.
\begin{haskell}
instance Monad (State s) where
  st >>= k = State (\s -> let (a, s') = runState st s
                          in runState (k a) s')
\end{haskell}
With \hask{pure} implemented in the \hask{Applicative} instance:
\begin{haskell}
  pure a = State (\s -> (a, s))
\end{haskell}

Applying bind to identity gives us the definition of \hask{join}:
\begin{haskell}
join :: State s (State s a) -> State s a
join mma = State (\s -> let (ma, s') = runState mma s
                        in runState ma s')
\end{haskell}
Notice that we are essentially passing the result of the first \hask{runState} to the second \hask{runState}, except that we have to uncurry the second one so it can accept a pair:
                             
\begin{haskell}
join mma = State (\s -> (uncurry runState) (runState mma s))
\end{haskell}
In this form, it's easy to convert it to point-free notation:
\begin{haskell}
join mma = State (uncurry runState . runState mma)
\end{haskell}

There are two basic Kleisli arrows (the first one, conceptually, coming from the terminal object \hask{()}) with which we can construct an arbitrary stateful computation. The first one retrieves the current state:
\begin{haskell}
get :: State s s
get = State (\s -> (s, s))
\end{haskell}
and the second one modifies it:
\begin{haskell}
set :: s -> State s ()
set s = State (\_ -> ((), s))
\end{haskell}
A lot of monads come with their own libraries of predefined basic Kleisli arrows.
\subsection{Nondeterminism}

For the list monad, let's consider how we would implement \hask{join}. It must turn a list of lists into a single list. This can be done by concatenating all the inner lists using the library function \hask{concat}. From there, we can derive the implementation of bind.
\begin{haskell}
instance Monad [] where
  as >>= k = concat (fmap k as)
\end{haskell}
\hask{pure} constructs a singleton list. (Thus a trivial version of nondeterminism is determinism.)
\begin{haskell}
  pure a = [a]
\end{haskell}

What imperative languages do using nested loops we can do in Haskell using the list monad. Think of \hask{as} in bind as aggregating the result of running the inner loop and \hask{k} as the code that runs in the outer loop. 

In many ways, Haskell's list behaves more like what is called an \index{iterator}\emph{iterator} or a \emph{generator} in imperative languages. Because of laziness, the elements of the list are rarely stored in memory all at once, so you may conceptualize a Haskell list as a pointer to the head together with a recipe for advancing it forward towards the tail. Or you may think of a list as a coroutine that produces, on demand, elements of a sequence.

\subsection{Continuation}

The implementation of bind for the continuation monad:
\begin{haskell}
newtype Cont r a = Cont { runCont :: (a -> r) -> r }
\end{haskell}
requires some backward thinking, because of the inherent inversion of control---the ``don't call us, we'll call you'' principle. 

The result of bind is of the type \hask{Cont r b}. To construct it, we need a function that takes, as an argument, a continuation \hask{k :: b -> r}:
\begin{haskell}
ma >>= fk = Cont (\k -> ...)
\end{haskell}
We have two ingredients at our disposal: 
\begin{haskell}
ma :: Cont r a
fk :: a -> Cont r b
\end{haskell}
We'd like to run \hask{ma}, and for that we need a continuation that would accept an \hask{a}.
\begin{haskell}
runCont ma (\a -> ...)
\end{haskell}
Inside it we can execute our \hask{fk}. The result is of the type \hask{Cont r b}, so we can run it with our continuation \hask{k :: b -> r}. 
\begin{haskell}
runCont (fk a) k
\end{haskell}

Taken together, this convoluted process produces the following implementation:
\begin{haskell}
instance Monad (Cont r) where
  ma >>= fk = Cont (\k -> runCont ma (\a -> runCont (fk a) k))
\end{haskell}
\hask{pure} comes from the \hask{Applicative} instance:
\begin{haskell}
  pure a = Cont (\k -> k a)
\end{haskell}
As mentioned earlier, composing continuations is not for the faint of heart. However, it has to be implemented only once---in the definition of the continuation monad. From there on, the \hask{do} notation will make the rest relatively easy.

\subsection{Input/Output}

The \hask{IO} monad's implementation is baked into the language. The basic I/O primitives are available through the library. They are either in the form of Kleisli arrows, or \hask{IO} objects (conceptually, Kleisli arrows from the terminal object \hask{()}). 

For instance, the following object contains a command to read a line from the standard input:
\begin{haskell}
getLine :: IO String
\end{haskell}
There is no way to extract the string from it, since it's not there yet; but the program can process it through a further series of Kleisli arrows. 

The \hask{IO} monad is the ultimate procrastinator: the composition of its Kleisli arrows piles up task after task to be executed later by the Haskell runtime.

To output a string followed by a newline, you can use this Kleisli arrow:
\begin{haskell}
putStrLn :: String -> IO ()
\end{haskell}
Combining the two, you may construct a simple \hask{main} object:
\begin{haskell}
main :: IO ()
main = getLine >>= putStrLn
\end{haskell}
which echoes a string you type.

Unlike the applicative, the monad lets us branch or pattern match on the intermediate values. In this example we are branching on the contents of an \hask{IO} object (we'll talk about the \hask{do} notation next):
\begin{haskell}
main :: IO ()
main = do
  s <- getLine
  if s == "yes"
  then putStrLn "Thank you!"
  else putStrLn "Next time."
\end{haskell}
Of course, the actual inspection of the value is postponed until the runtime runs the interpreter over the resulting \hask{IO} object. 


\section{Do Notation}

It's worth repeating that the sole purpose of monads in programming is to let us decompose one big Kleisli arrow into multiple smaller ones. 

This can be done either directly, in a point-free style, using Kleisli composition \hask{<=<}; or by naming intermediate values and binding them to Kleisli arrows using \hask{>>=}. 

Some Kleisli arrows are defined in libraries, others are reusable enough to warrant out-of-line implementation but, in practice, the majority are just single-shot inline lambdas.

Here's a simple example:
\begin{haskell}
main :: IO ()
main = 
  getLine >>= \s1 ->
    getLine >>= \s2 ->
      putStrLn ("Hello " ++ s1 ++ " " ++ s2)
\end{haskell}
which uses an ad-hoc Kleisli arrow of the type \hask{String->IO ()} defined by the lambda expression:
\begin{haskell}
\s1 ->
    getLine >>= \s2 ->
      putStrLn ("Hello " ++ s1 ++ " " ++ s2)
\end{haskell}
The body of this lambda is further decomposed using another ad-hoc Kleisli arrow:
\begin{haskell}
\s2 -> putStrLn ("Hello " ++ s1 ++ " " ++ s2)
\end{haskell}

Such constructs are so common that there is special syntax called the \hask{do} notation that cuts through a lot of boilerplate. The above code, for instance, can be written as:
\begin{haskell}
main = do
  s1 <- getLine
  s2 <- getLine
  putStrLn ("Hello " ++ s1 ++ " " ++ s2)
\end{haskell}
The compiler will automatically convert it to a series of nested lambdas. The line \hask{ s1<-getLine } is usually read as: ``\hask{s1} \emph{gets} the result of \hask{getLine}.''

Here's another example: a function that uses the list monad to generate all possible pairs of elements taken from two lists.
\begin{haskell}
pairs :: [a] -> [b] -> [(a, b)]
pairs as bs = do
  a <- as
  b <- bs
  pure (a, b)
\end{haskell}
Notice that the last line in a \hask{do} block must produce a monadic value---here this is accomplished using \hask{pure}.



Most imperative languages lack the abstraction power to generically define a monad, and instead they attempt to hard-code some of the more common monads. For instance, they implement exceptions as an alternative to the \hask{Either} monad, or concurrent tasks as an alternative to the continuation monad. Some, like C++, introduce coroutines that mimic Haskell's \hask{do} notation. 

\begin{exercise}
Implement:
\begin{haskell}
ap :: Monad m => m (a -> b) -> m a -> m b
\end{haskell}
using the \hask{do} notation.
\end{exercise}

\begin{exercise}
Rewrite the \hask{pairs} function using the bind operators and lambdas.
\end{exercise}

\section{Continuation Passing Style}

I mentioned before that the \hask{do} notation provides the syntactic sugar that makes working with continuations more natural. One of the most important applications of continuations is in transforming programs to use CPS (continuation passing style). The CPS transformation is common in compiler construction. Another very important application of CPS is in converting recursion to iteration. 

The common problem with deeply recursive programs is that they may blow the runtime stack. A function call usually starts by pushing function arguments, local variables, and the return address on the stack. Thus deeply nested recursive calls may quickly exhaust the (usually fixed-size) runtime stack resulting in a runtime error. This is the main reason why imperative languages prefer looping to recursion, and why most programmers learn about loops before they study recursion. However, even in imperative languages, when it comes to traversing recursive data structures, such as linked lists or trees, recursive algorithms are more natural.

The problem with using loops, though, is that they require mutation. There is usually some kind of a counter or a pointer that is advanced and checked with each turn of the loop. This is why purely functional languages that shun mutation must use recursion in place of loops. But since looping is more efficient and it doesn't consume the runtime stack, the compiler tries to covert recursive calls to loops. In Haskell all tail-recursive functions are turned into loops. 

\subsection{Tail recursion and CPS}

\index{tail recursion}Tail recursion means that the recursive call happens at the very end of the function. The function doesn't perform any additional operations on the result of the tail call. For instance this program is not tail recursive, because it has to add \hask{i} to the result of the recursive call:
\begin{haskell}
sum1 :: [Int] -> Int
sum1 [] = 0
sum1 (i : is) = i + sum1 is
\end{haskell}
In contrast, the following implementation is tail recursive because the result of the recursive call to \hask{go} is returned without further modification:
\begin{haskell}
sum2 = go 0 
  where go n [] = n
        go n (i : is) = go (n + i) is
\end{haskell}
The compiler can easily turn the latter into a loop. Instead of making the recursive call, it will overwrite the value of the first argument \hask{n} with \hask{n + i}, overwrite the pointer to the head of the list with the pointer to its tail, and then jump to the beginning of the function. 

Note however that it doesn't mean that the Haskell compiler won't be able to cleverly optimize the first implementation. It just means that the second implementation, which is tail recursive, is \emph{guaranteed} to be turned into a loop.

In fact, it's always possible to turn recursion into tail recursion by performing the CPS transformation. This is because a continuation encapsulates \emph{the rest of the computation}, so it's always the last call in a function. 

To see how it works in practice, consider a simple tree traversal. Let's define a tree that stores strings in both nodes and leaves:
\begin{haskell}
data Tree = Leaf String 
          | Node Tree String Tree
\end{haskell}
To concatenate all these strings we use the traversal that first recurses into the left subtree, and then into the right subtree:
\begin{haskell}
show :: Tree -> String
show (Node lft s rgt) =
  let ls = show lft
      rs = show rgt
  in ls ++ s ++ rs
\end{haskell}
This is definitely not a tail recursive function, and it's not obvious how to turn it into one. However, we can almost mechanically rewrite it using the continuation monad:
\begin{haskell}
showk :: Tree -> Cont r String
showk (Leaf s) = pure s
showk (Node lft s rgt) = do
  ls <- showk lft
  rs <- showk rgt
  pure (ls ++ s ++ rs)
 \end{haskell}
We can then run the resulting function with the trivial continuation \hask{id}:
\begin{haskell}
show :: Tree -> String
show t = runCont (showk t) id
\end{haskell}

This implementation is automatically tail recursive. We can see it clearly by desugaring the do notation:
\begin{haskell}
showk :: Tree -> (String -> r) -> r
showk (Leaf s) k = k s
showk (Node lft s rgt) k =
  showk lft (\ls -> 
    showk rgt (\rs -> 
      k (ls ++ s ++ rs)))
\end{haskell}
Let's analyze this code. The function calls itself, passing the left subtree \hask{lft} and the following continuation:
\begin{haskell}
\ls -> 
    showk rgt (\rs -> 
      k (ls ++ s ++ rs))
\end{haskell}
This lambda in turn calls \hask{showk} with the right subtree \hask{rgt} and another continuation:
\begin{haskell}
\rs -> k (ls ++ s ++ rs)
\end{haskell}
This innermost lambda that has access to all three strings: left, middle, and right. It concatenates them and calls the outermost continuation \hask{k} with the result.

In each case, the recursive call to \hask{showk} is the last call, and its result is immediately returned. Moreover, the type of the result is the generic type \hask{r}, which in itself guarantees that we can't perform any operations on it, even if we wanted to. 

When we finally run the result of \hask{showk}, we pass it the identity (instantiated for the \hask{String} type):
\begin{haskell}
show :: Tree -> String
show t = runCont' (showk t) id
  where runCont' cont k = cont k
\end{haskell}

\subsection{Using named functions}

But suppose that our programming language doesn't support anonymous functions. Is it possible to replace the lambdas with named functions? We've done this before when we discussed the adjoint functor theorem. We notice that the lambdas generated by the continuation monad are closures---they capture some values from their environment. If we want to replace them with named functions, we'll have to pass the environment explicitly. 

Let's replace the first lambda with the call to the function named \hask{next}, and pass it the necessary environment in the form or a tuple of three values \hask{(s, rgt, k)}:
\begin{haskell}
showk :: Tree -> (String -> r) -> r
showk (Leaf s) k = k s
showk (Node lft s rgt) k =
  showk lft (next (s, rgt, k))
\end{haskell}
The three values are the string from the current node of the tree, the right subtree, and the outer continuation. 

The function \hask{next} makes the recursive call to \hask{showk} passing to it the right subtree and a named continuation named \hask{conc}:
\begin{haskell}
next :: (String, Tree, String -> r) -> String -> r
next (s, rgt, k) ls = showk rgt (conc (ls, s, k))
\end{haskell}
Again, \hask{conc} explicitly captures the environment containing two strings and the outer continuation. It performs the concatenation and calls the outer continuation with the result:
\begin{haskell}
conc :: (String, String, String -> r) -> String -> r
conc (ls, s, k) rs = k (ls ++ s ++ rs)
\end{haskell}
Finally, we define the trivial identity continuation:
\begin{haskell}
done :: String -> String
done s = s
\end{haskell}
that we use to extract the final result:
\begin{haskell}
show t = showk t done
\end{haskell}

\subsection{Defunctionalization}

Continuation passing style requires the use of higher order functions. If this is a problem, e.g., when implementing distributed systems, we can always use the adjoint functor theorem to defunctionalize our program. 

The first step is to create the sum of all relevant environments, including the empty one we used in \hask{done}:
\begin{haskell}
data Kont = Done 
          | Next String Tree Kont 
          | Conc String String Kont
\end{haskell}
Notice that this recursive data structure can be reinterpreted as a list or a stack. 
\begin{haskell}
data Kont = Done | Cons Sum Kont
\end{haskell}
where:
\begin{haskell}
data Sum = Next' String Tree  | Conc' String String 
\end{haskell}
This list is our version of the runtime stack necessary to implement a recursive algorithm. 

Since we are only interested in producing a string as the final result, we're going to approximate the \hask{String -> String} function type. This is the approximate counit of the adjunction that defines it (see the adjoint functor theorem):
\begin{haskell}
apply :: (Kont, String) -> String
apply (Done, s) = s
apply (Next s rgt k, ls) = showk rgt (Conc ls s k)
apply (Conc ls s k, rs) = apply (k, ls ++ s ++ rs)
\end{haskell}

The \hask{showk} function can be now implemented without recourse to higher order functions:
\begin{haskell}
showk :: Tree -> Kont -> String
showk (Leaf s) k = apply (k, s)
showk (Node lft s rgt) k = showk lft (Next s rgt k)
\end{haskell}
To extract the result, we call it with \hask{Done}:
\begin{haskell}
showTree t = showk t Done
\end{haskell}

\section{Monads Categorically}

In category theory monads first arose in the study of algebras. In particular, the bind operator can be used to implement the very important operation of substitution. 

\subsection{Substitution}

Consider this simple expression type. It's parameterized by the type \hask{x} that we can use for naming our variables:
\begin{haskell}
data Ex x = Val Int 
          | Var x 
          | Plus (Ex x) (Ex x) 
 deriving (Functor, Show)
\end{haskell}
We can, for instance, construct an expression $(2 + a) + b$:
\begin{haskell}
ex :: Ex Char
ex = Plus (Plus (Val 2) (Var 'a')) (Var 'b')
\end{haskell}
We can implement the \hask{Monad} instance for \hask{Ex}:
\begin{haskell}
instance Monad Ex where
  Val n >>= k = Val n
  Var x >>= k = k x
  Plus e1 e2 >>= k = 
    let x = e1 >>= k
        y = e2 >>= k
    in (Plus x y)
\end{haskell}
with:    
\begin{haskell}
  pure x = Var x 
\end{haskell}

Now suppose that you want to make a substitution by replacing the variable $a$ with $x_1 + 2$ and $b$ with $x_2$ (for simplicity, let's not worry about other letters of the alphabet). This substitution is represented by the Kleisli arrow \hask{sub}:
\begin{haskell}
sub :: Char -> Ex String
sub 'a' = Plus (Var "x1") (Val 2)
sub 'b' = Var "x2"
\end{haskell}
As you can see, we were even able to change the type used for naming variables from \hask{Char} to \hask{String}.

When we bind this Kleisli arrow to \hask{ex}:
\begin{haskell}
ex' :: Ex String
ex' = ex >>= sub
\end{haskell}
we get, as expected, a tree corresponding to $(2 + (x_1 + 2)) + x_2$.

\subsection{Monad as a monoid}

Let's analyze the definition of a monad that uses \hask{join}:
\begin{haskell}
class Functor m => Monad m where
  join :: m (m a) -> m a
  pure :: a -> m a
\end{haskell}
We have an endofunctor \hask{m} and two polymorphic functions. 

In category theory, the functor that defines the monad is traditionally denoted by $T$ (probably because monads were initially called ``triples''). The two polymorphic functions become natural transformations. The first one, corresponding to \hask{join}, maps the ``square'' of $T$ (a composition of $T$ with itself) to $T$:
\[ \mu \colon T \circ T \to T \]
(Of course, only \emph{endo}-functors can be squared this way.) 

The second, corresponding to \hask{pure}, maps the identity functor to $T$:
\[ \eta \colon \text{Id} \to T \]

Compare this with our earlier definition of a monoid in a monoidal category:
\begin{align*}
\mu &\colon m \otimes m \to m \\
\eta &\colon I \to m
\end{align*}
The similarity is striking. This is why we often call the natural transformation $\mu$ the \emph{monadic multiplication}. But in what category can the composition of functors be considered a tensor product? 

Enter the category of endofunctors. Objects in this category are endofunctors and arrows are natural transformations. 

But there's more structure to that category. We know that any two endofunctors can be composed. How can we interpret this composition if we want to treat endofunctors as objects? An operation that takes two objects and produces a third object looks like a tensor product.  The only condition imposed on a tensor product is that it's functorial in both arguments. That is, given a pair of arrows:
\begin{align*}
 \alpha &\colon T \to T' \\
 \beta &\colon S \to S' 
\end{align*}
 we can lift it to the mapping of the tensor product:
 \[ \alpha \otimes \beta \colon T \otimes S \to T' \otimes S' \]
 
 In the category of endofunctors, the arrows are natural transformations so, if we replace $\otimes$ with $\circ$, the lifting is the mapping:
\[ \alpha \circ \beta \colon T \circ T' \to S \circ S' \]
But this is just horizontal composition of natural transformations (now you understand why it's denoted by a circle).

The unit object in this monoidal category is the identity endofunctor, and unit laws are satisfied ``on the nose,'' meaning
\[ \text{Id} \circ T = T = T \circ \text{Id}\]
We don't need any unitors. We don't need any associators either, since functor composition is automatically associative. 

A monoidal category in which unitors and associators are identity morphisms is called a \index{strict monoidal category}\emph{strict} monoidal category.

Notice, however, that composition is not symmetric, so this is not a symmetric monoidal category.

So, all said, a monad is a monoid in the monoidal category of endofunctors. 

A monad $(T, \eta, \mu)$ consists of an object in the category of endofunctors---meaning an endofunctor $T$; and two arrows---meaning natural transformations:
\begin{align*}
 \eta &\colon \text{Id} \to T \\
 \mu &\colon T \circ T \to T 
\end{align*}
For this to be a monoid, these arrows must satisfy monoidal laws. Here are the unit laws (with unitors replaced by strict equalities):
\[
 \begin{tikzcd}
\text{Id} \circ T
 \arrow[rr, "\eta \circ T"]
 \arrow[rrd, "="']
& & T \circ T
 \arrow[d, "\mu"]
&& T \circ \text{Id}
 \arrow[ll, "T \circ \eta"']
 \arrow[lld, "="]
 \\
 && T
  \end{tikzcd}
\]
and this is the associativity law:
\[
 \begin{tikzcd}
 (T \circ T) \circ T 
 \arrow[rr, "="]
 \arrow[d, "\mu \circ T"]
 &&
 T \circ (T \circ T)
 \arrow[d, "T \circ \mu"]
 \\
 T \circ T 
 \arrow[dr, "\mu"]
& & T \circ T
 \arrow[dl, "\mu"']
 \\
&  T
 \end{tikzcd}
\]
We used the whiskering notation for horizontal composition of $\mu \circ T$ and $T \circ \mu$.

These are the monad laws in terms of $\mu$ and $\eta$. They can be directly translated to the laws for \hask{join} and \hask{pure}. They are also equivalent to the laws of the Kleisli category built from arrows $a \to T b$.

\section{Free Monads}

A monad lets us specify a sequence of actions that may produce side effects. Such a sequence tells the computer both what to do and how to do it. But sometimes more flexibility is required: We'd like to separate the ``what'' from the ``how." A free monad lets us produce the sequence without committing to a particular monad for its execution. This is analogous to defining a free monoid (a list), which lets us postpone the choice of the algebra to apply to it; or to creating an AST (abstract syntax tree) before compiling it to executable code.

Free constructions are defined as left adjoints to forgetful functors. So first we have to define what it means to forget to be a monad. Since a monad is an endofunctor equipped with additional structure, we'd like to forget this structure. We take a monad $(T, \eta, \mu)$ and keep only $T$. But in order to define such a mapping as a functor, we first need to define the category of monads.

\subsection{Category of monads}

The objects in the category of monads $\mathbf{Mon}(\cat C)$ are monads $(T, \eta, \mu)$. We can define an arrow between two monads $(T, \eta, \mu)$ and $(T', \eta', \mu')$ as a natural transformation between the two endofunctors:
\[ \lambda \colon T \to T' \]
However, since monads are endofunctors \emph{with structure}, we want these natural transformations to preserve the structure. Preservation of unit means that the following diagram must commute:
\[
 \begin{tikzcd}
&\text{Id}
 \arrow[ld, "\eta"']
 \arrow[rd, "\eta'"]
 \\
 T
 \arrow[rr, "\lambda"]
 && T'
 \end{tikzcd}
\]
Preservation of multiplication means that the following diagram must commute:
\[
 \begin{tikzcd}
 T \circ T
 \arrow[r, "\lambda \circ \lambda"]
 \arrow[d, "\mu"]
 & T' \circ T'
 \arrow[d, "\mu'"]
 \\
 T
 \arrow[r, "\lambda"]
 & T'
 \end{tikzcd}
\]

Another way of looking at $\mathbf{Mon}(\cat C)$ is that it's a category of monoids in the monoidal category $([\cat C, \cat C], \circ, \text{Id})$. 

\subsection{Free monad}

Now that we have a category of monads, we can define the forgetful functor:
\[ U \colon \mathbf{Mon}(\cat C) \to [\cat C, \cat C] \]
that maps every triple $(T, \eta, \mu)$ to $T$ and every monad morphism to the underlying natural transformation.

We would like a free monad to be generated by a left adjoint to this forgetful functor. The problem is that this left adjoint doesn't always exist. As usual, this is related to size issues: monads tend to blow things up. The bottom line is that free monads exist for some, but not all, endofunctors. Therefore we can't define a free monad through an adjunction. Fortunately, in most cases of interest, a free monad can be defined as a fixed point of an algebra. 

The construction is analogous to how we defined a free monoid as an initial algebra for the list functor:
\begin{haskell}
data ListF a x = NilF | ConsF a x
\end{haskell}
or the more general functor:
\[ F_a x = I + a \otimes x \]
in a monoidal category $(\cat C, \otimes, I)$.

This time, however, the monoidal category in which a monad is defined as a monoid is the category of endofunctors $([\cat C, \cat C], \circ, \text{Id})$. A free monoid in this category is the initial algebra for the higher order ``list'' functor that maps functors to functors:
\[ \Phi_F G = \text{Id} + F \circ G \]
Here, the \index{coproduct of functors}coproduct of two functors is defined point-wise. On objects:
\[ (F + G) a = F a + G a \]
and on arrows:
\[ (F + G) f = F f + G f \]
(We form a coproduct of two morphisms using the functoriality of the coproduct. We assume that $\cat C$ is co-cartesian, that is all coproducts exist.)


The initial algebra is the (least) fixed point of this operator, or the solution to the recursive equation:
\[ L_F \cong \text{Id} + F \circ L_F \]
This formula establishes a natural isomorphism between two functors. 



\subsection{Free Monad in Haskell}

In category theory, a functor is just a mapping between two categories. In Haskell, if we want to implement anything more advanced than a simple Haskell endofunctor, we have to introduce some new classes. A Haskell functor is a type constructor---that is the mapping of types to types:
\begin{haskell}
f :: Type -> Type
\end{haskell}
together with an implementation of \hask{fmap}--- that is the mapping of functions to functions. 

A \index{higher order functor}higher order functor maps functors to functors. So it's a type constructor that takes a type constructor and produces another type constructor:
\begin{haskell}
hf :: (Type -> Type) -> (Type -> Type)
\end{haskell}
It must also map natural transformations to natural transformations. To implement it in Haskell, we define a new type class:
\begin{haskell}
class HFunctor (hf :: (Type -> Type) -> Type -> Type) where
   hmap :: (Functor f, Functor g) => 
       Natural f g -> Natural (hf f) (hf g)
\end{haskell}

Our higher order list functor:
\[ \Phi_F G = \text{Id} + F \circ G \]
is such an \hask{HFunctor}, which additionally depends on yet another type constructor \hask{f}. Since it's a sum type, it will have two constructors corresponding to two injections:
\begin{haskell}
data Phi f g a where
   IdF :: a -> Phi f g a
   CompF :: f (g a) -> Phi f g a
\end{haskell}
Given a natural transformation \hask{alpha:: Nat g h}, it produces another natural transformation \hask{Nat (Phi f g) (Phi f h)}:
\begin{haskell}
instance Functor f => HFunctor (Phi f) where
   hmap :: (Functor f, Functor g, Functor h) =>
          Natural g h -> Natural (Phi f g) (Phi f h)
   hmap alpha (IdF a) = IdF a
   hmap alpha (CompF fga) = CompF (fmap alpha fga)
\end{haskell}
This is just the application of the functoriality of the coproduct and that of functor composition.

We have to separately assert the functoriality of the result of applying \hask{Phi f} to a functor \hask{g}:
\begin{haskell}
instance (Functor f, Functor g) => Functor (Phi f g) where
   fmap h (IdF a) = IdF (h a)
   fmap h (CompF fga) = CompF (fmap (fmap h) fga)
\end{haskell}



The isomorphism that generates the free monad:
\[ L_F \cong \text{Id} + F \circ L_F \]
can be seen as a definition of a recursive data type. Going from right to left, we have the natural transformation, which we recognize as the structure map of the initial algebra:
\[\iota \colon \text{Id} + F \circ L_F \to L_F\]
It's a mapping out of the sum, so it's equivalent to a pair of natural transformations:
\begin{align*}
\eta &\colon \text{Id} \to L_F
\\
\varphi &\colon F \circ L_F \to L_F
\end{align*}

When translating this to Haskell, the components of these transformations become two constructors. They define the following recursive data type parameterized by a functor \hask{f}:
\begin{haskell}
data FreeMonad f a where
   Pure :: a -> FreeMonad f a
   Free :: f (FreeMonad f a) -> FreeMonad f a
\end{haskell}

If we think of the functor \hask{f} as a container of values, the constructor \hask{Free} takes a functorful of \hask{(FreeMonad f a)} and stashes it away. A value of the type \hask{FreeMonad f a} is therefore a tree in which every node is a functorful of branches, and each leaf contains a value of the type \hask{a}.

\hask{FreeMonad} is a higher order functor:
\begin{haskell}
instance HFunctor FreeMonad where
   hmap :: (Functor f, Functor g) =>
      Natural f g -> Natural (FreeMonad f) (FreeMonad g)
   hmap _ (Pure a) = Pure a
   hmap alpha (Free ffa) = Free (alpha (fmap (hmap alpha) ffa))
\end{haskell}

It's result is a \hask{Functor}:
\begin{haskell}
instance Functor f => Functor (FreeMonad f) where
  fmap g (Pure a) = Pure (g a)
  fmap g (Free ffa) = Free (fmap (fmap g) ffa)
\end{haskell}
Here, the outer \hask{fmap} uses the \hask{Functor} instance of \hask{f}, while the inner, \hask{fmap g}, recurses into the branches.

By construction, a \hask{FreeMonad} is a \hask{Monad}. The monadic unit \hask{eta} is just a thin encapsulation of the identity functor:
\begin{haskell}
eta :: a -> FreeMonad f a
eta a = Pure a
\end{haskell}

Monadic multiplication, or \hask{join}, is defined recursively:
\begin{haskell}
mu :: Functor f => FreeMonad f (FreeMonad f a) -> FreeMonad f a
mu (Pure fa) = fa
mu (Free ffa) = Free (fmap mu ffa)
\end{haskell}

The \hask{Monad} instance for \hask{FreeMonad f} is therefore:
\begin{haskell}
instance Functor f => Monad (FreeMonad f) where
  m >>= k = mu (fmap k m)
\end{haskell}
with:
\begin{haskell}
  pure a = eta a
\end{haskell}

We can also define bind directly:
\begin{haskell}
  (Pure a)   >>= k = k a
  (Free ffa) >>= k = Free (fmap (>>= k) ffa)
\end{haskell}

A free monad accumulates monadic actions in a tree-like structure without committing to any particular evaluation strategy. This tree can be ``interpreted'' using an algebra. But this time it's an algebra in the category of endofunctors, so its carrier is an endofunctor $G$ and the structure map $\alpha$ is a natural transformation $\Phi_F G \to G$:
\[ \alpha \colon \text{Id} + F \circ G \to G\]
This natural transformation, being a mapping out of a sum, is equivalent to a pair of natural transformations :
\begin{align*}
\lambda &\colon \text{Id} \to G
\\
\rho &\colon F \circ G \to G
\end{align*}

We can translate it to Haskell as a pair of polymorphic functions:
\begin{haskell}
type MAlg f g a = (a -> g a, f (g a) -> g a)
\end{haskell}

Since the free monad is the initial algebra, there is a unique mapping, the catamorphism, from it to any other algebra. Recall how we defined a catamorphism for a regular algebras:
\begin{haskell}
cata :: Functor f => Algebra f a -> Fix f -> a
cata alg = alg . fmap (cata alg) . out
\end{haskell}

An analogous diagram defines a catamorphism for a free monad:
\[
 \begin{tikzcd}
 \text{Id} + F \circ L_F
 \arrow[rr, "{\text{hmap} (\text{mcata}\, \alpha)}"]
 \arrow[d, "{\iota = \langle \eta, \varphi \rangle}"]
 && \text{Id} + F \circ G
\arrow[d, "{\alpha = \langle \lambda, \rho \rangle}"]
 \\
 L_F
 \arrow[rr, dashed, "\text{mcata}\, \alpha"]
 && G
  \end{tikzcd}
\]

In Haskell, we implement it by pattern-matching on the two constructors of the free monad (this corresponds to inverting the initial algebra $\iota$). If it's a leaf, we apply $\lambda$ to it. If it's a node, we recursively process its contents, and apply $\rho$ to the result:
\begin{haskell}
mcata :: Functor f => MAlg f g a -> FreeMonad f a -> g a
mcata (l, r) (Pure a) = l a
mcata (l, r) (Free ffa) = 
  r (fmap (mcata (l, r)) ffa)
\end{haskell}

Many tree-like monads are in fact free monads for simple functors. On the other hand, the list monad is not free because its \hask{join} irreversibly smashes the lists together.

\begin{exercise}
A (non-empty) rose tree is defined as:
\begin{haskell}
data Rose a = Leaf a | Rose [Rose a]
  deriving Functor
\end{haskell}
Implement conversions back and forth between \hask{Rose a} and  \hask{FreeMonad [] a}.
\end{exercise}

\begin{exercise}
Implement conversions between a non-empty binary tree and \hask{FreeMonad Bin a}, where:
\begin{haskell}
data Bin a = Bin a a
\end{haskell}
\end{exercise}

\subsection{Stack calculator example}
As an example, let's consider a stack calculator implemented as an embedded domain-specific language, EDSL. We'll use the free monad to accumulate simple commands written in this language. 

The commands are defined by the functor \hask{StackF}. Think of the parameter  \hask{k} as the continuation. 
\begin{haskell}
data StackF k  = Push Int k
               | Top (Int -> k)
               | Pop k            
               | Add k
               deriving Functor
\end{haskell}
For instance, \hask{Push} is supposed to push an integer on the stack and then call the continuation \hask{k}.

The free monad for this functor can be thought of as a tree, with most branches having just one child, thus forming lists. The exception is the \hask{Top} node, which has many children, one per every value of \hask{Int}.

Here's the free monad for this functor:
\begin{haskell}
type FreeStack = FreeMonad StackF
\end{haskell}

In order to create domain-specific programs we'll define a few helper functions. There is a generic one that lifts a functorful of values to a free monad:
\begin{haskell} 
liftF :: (Functor f) => f r -> FreeMonad f r
liftF fr = Free (fmap Pure fr)
\end{haskell}
We also need a series of ``smart constructors,'' which are Kleisli arrows for our free monad:
\begin{haskell}
push :: Int -> FreeStack ()
push n = liftF (Push n ())

pop :: FreeStack ()
pop = liftF (Pop ())

top :: FreeStack Int
top = liftF (Top id)

add :: FreeStack ()
add = liftF (Add ())
\end{haskell}

Since a free monad is a monad, we can conveniently combine Kleisli arrows using the \hask{do} notation. For instance, here's a toy program that adds two numbers and returns their sum:
\begin{haskell}
calc :: FreeStack Int
calc = do
  push 3
  push 4
  add
  x <- top
  pop
  pure x
\end{haskell}

In order to execute this program, we need to define an algebra whose carrier is an endofunctor. Since we want to implement a stack-based calculator, we'll use a version of the state functor. Its state is a stack---a list of integers. The state functor is defined as a function type; here it's a function that takes a list and returns a new list coupled with the type parameter \hask{k}:
\begin{haskell}
newtype StackAction k = St ([Int] -> ([Int], k))
  deriving Functor
\end{haskell}

To run the action, we apply the function to the stack:
\begin{haskell}
runAction :: StackAction k -> [Int] -> ([Int], k)
runAction (St act) ns = act ns
\end{haskell}

We define the algebra as a pair of polymorphic functions corresponding to the two constructors of the free monad, \hask{Pure} and \hask{Free}:
\begin{haskell}
runAlg :: MAlg StackF StackAction a
runAlg = (stop, go)
\end{haskell}
The first function terminates the execution of the program and returns a value:
\begin{haskell}
stop :: a -> StackAction a
stop a = St (\xs -> (xs, a))
\end{haskell}
The second function pattern matches on the type of the command. Each command carries with it a continuation. This continuation has to be run with a (potentially modified) stack. Each command modifies the stack in a different way:
\begin{haskell}
go :: StackF (StackAction k) -> StackAction k
go (Pop k)    = St (\ns -> runAction k (tail ns))
go (Top ik)   = St (\ns -> runAction (ik (head ns)) ns)
go (Push n k) = St (\ns -> runAction k (n: ns))
go (Add k)    = St (\ns -> runAction k 
                   ((head ns + head (tail ns)): tail (tail ns)))
\end{haskell}
For instance, \hask{Pop} discards the top of the stack. \hask{Top} takes an integer from top of the stack and uses it to pick the branch to be executed. It does it by applying the function \hask{ik} to the integer. \hask{Add} adds the two numbers at the top of the stack and pushes the result. 

Notice that the algebra we have defined does not involve recursion. Separating recursion from the actions is one of the advantages of the free monad approach. The recursion is instead encoded once and for all in the catamorphism. 

Here's the function that can be used to run our toy program:
\begin{haskell}
run :: FreeMonad StackF k -> ([Int], k)
run prog = runAction (mcata runAlg prog) [] 
\end{haskell}

Obviously, the use of partial functions \hask{head} and \hask{tail} makes our interpreter fragile. A badly formed program will cause a runtime error. A more robust implementation would use an algebra that allows for error propagation.

The other advantage of using free monads is that the same program may be interpreted using different algebras.

\begin{exercise}
Implement a ``pretty printer'' that displays the program constructed using our free monad. Hint: Implement the algebra that uses the \hask{Const} functor as the carrier:
\begin{haskell}
showAlg :: MAlg StackF (Const String) a
\end{haskell}
\end{exercise}



\end{document}